//************************************************************
//    > File Name: remove-nth-node-from-end-of-list.cpp
//    > Author: davis
//    > Mail:  
//    > Created Time: 2017年03月28日 10:26:09
//***********************************************************
//lintcode #174
#include<bits/stdc++.h>
using namespace std;
class ListNode{
	public:
		int val;
		ListNode *next;
		ListNode(int val){
			this->val=val;
			this->next=NULL;
		}
};
ListNode *create(vector<int> &v){
	ListNode H(-1);
	int i=0;
	for(ListNode *p=&H;i<v.size();++i){
		p->next=new ListNode(v[i]);
		p=p->next;
	}
	return H.next;
}
void clean(ListNode *l){
	for(ListNode *tmp;l;){
		tmp=l;
		l=l->next;
		delete tmp;
	}
}
ListNode *removeNthFromEnd(ListNode *head,int n){
	if(head==NULL || n<1)
		return head;
	ListNode *slow,*fast;
	for(fast=head,slow=head;fast&&n>=0;fast=fast->next,--n);
	cout<<"n="<<n<<endl;
	if(n==0){
		ListNode *t=head;
		head=head->next;
		delete t;
	}
	else{
		for(;fast;slow=slow->next,fast=fast->next);
		ListNode *tmp=slow->next;
		slow->next=slow->next->next;
		delete tmp;
		return head;
	}
	return head;
}
int main(){
	vector<int> a={
		1,2,3,4,5
	};
	ListNode *l=create(a);
	cout<<"create listnode"<<endl;
	ListNode *r=removeNthFromEnd(l,5);
	for(;r;r=r->next)
		cout<<r->val<<" ";
	cout<<endl;
	clean(r);
}
